Various mechanisms have been developed for managing objects in an object-oriented environment. One of the most efficient and popular techniques of managing objects with efficient memory usage is known as “reference counting.”
FIG. 1 is a diagram illustrating an exemplary implementation of the reference counting technique. Consider an implementation of an object storing a string. One technique for implementing the reference counting technique would be to generate a data structure 102 including a wrapper structure 104 and a representation structure 106. The wrapper structure 104 references the representation structure 106 (e.g., via a pointer 105 to the memory location of the representation structure 106). For instance, the wrapper structure 104 may be an object. A single representation structure 106 may have multiple wrapper structures pointing to it (not shown to simplify illustration). The representation structure 106 contains the actual data bits (such as the string data in this example) and a reference counter 108 (e.g., variable) that enumerates all wrapper structures pointing to the same representation structure 106. The data 110 (e.g., string) is accessed by a data pointer 112 of the representation structure 106. In this example, the data 110 stored is the string “This is a string.” The data 110 may be stored in a data structure such as an object. Both the wrapper structure 104 and representation structure 106 may therefore be implemented as objects.
The goal of reference counting is to reduce the costs both in time and memory for operations such as copying and sharing data structures. For example, if a programmer wishes to duplicate a string, instead of duplicating the entire memory occupied by the string's characters, the reference counter 108 of the representation structure 106 is incremented by one.
FIG. 2 is a diagram illustrating an exemplary implementation 200 of the reference counting technique after a copy operation has been performed. Consider an object A of type string that represents a string “This is a string.” In this example, object A 202 is the wrapper structure that points to the representation structure 204 including a reference counter 206 equal to 1 and a pointer 208 to the string “This is a string.”
Application of a copy operation (duplication) of the data (e.g., string) will generate a second wrapper structure 210, object B, which points to the representation structure 204 (typically to the memory location of the representation structure 204). In addition, the reference counter 206 is incremented to 2, indicating that two different wrapper structures (or objects) refer to the representation structure 204. Thus, using the reference counting technique, the same data is shared between two objects efficiently. Another advantage of the reference counting technique is that representation structures can be relocated in memory (e.g., to optimize memory consumption via memory recycling algorithms) while maintaining a reference to the representation structures.
Data or associated objects may be used as keys for use in accessing other data via a data structure such as a table or associative dictionary. Data structures such as associative dictionaries create a one-to-one relationship between a set of keys and a set of values such that one of the set of keys can be used to retrieve a corresponding one of the set of values.
One example of a specific implementation of an associative dictionary is an array, where a set of keys corresponds to a set of integer values. Another example of an associative dictionary is a dictionary that maps strings to numbers denoting the number of words in the string. For instance, the string “A string” may be used as a key to access the number 2. In such a dictionary, the string key “count these words” corresponds to an integer 3, which may be stored in an object.
Implementing associative dictionaries in an environment that uses reference-counted objects presents a significant problem. As described above, an associative dictionary creates a one-to-one relationship between keys and corresponding values. Sometimes, it is desirable to use an object as a key to access a corresponding value in an associative dictionary. For instance, an application might compute a function that takes a string object as an argument and performs calculations using this string object. To save execution time upon the next invocation of this function, it may be desirable to store the argument and the result of this function in the cache. Thus, there is a need to reliably identify such key objects.
As set forth above, wrapper structures are generally pointers to the memory location of the representation structure. By de-referencing these pointers, it is possible to ascertain whether two wrapper structures point to the same memory location and therefore point to the same object. However, sometimes it may be desirable to optimize programs' memory usage by relocating some objects to a memory area different from where these objects were originally stored. Since memory may be recycled or otherwise optimized, the address of the representation structure may not remain the same. As a result, the memory address of the representation structure is not the optimal identifier for use as a key in an associative dictionary.
In addition to using the memory address for the purpose of identifying a key in an associative dictionary, it is also possible to perform a computational calculation on the key object, which is commonly referred to as “hashing” or “calculating the hash value.” However, problems associated with hashing include collisions and computational complexity. A collision occurs when two different objects have an identical hash value. Since associative dictionaries define a one-to-one mapping between key objects and corresponding values, collisions can cause critical errors in the implementation of associative dictionaries. Even if collisions could be avoided, the computational complexity of calculating hash functions typically slows programs down.